package binaryTree.ClosestCommonAncestor;

import binaryTree.TreeNode;

public class LookElement {

    boolean flag=false;
    TreeNode res=new TreeNode();
    public  TreeNode find(TreeNode root,int target){
        if (root==null){
            return  null;
        }
        find1(root, target);

        if (flag==false){
            return  null;
        }
        return res;
    }

    public void  find1(TreeNode root,int target){
        if (root==null){
            return;
        }
        if (root.val==target){
            flag=true;
           res=root;
          return;
        }
        find1(root.left, target);

        //todo:如果不加入这个判断　　即使找到了符合目标值的节点　
        // 也还会查找右子树　　加上后就不会再查找了　　这样与下面的效率几乎差不多了

        if (flag==true){
            return;
        }
        find1(root.right, target);
    }

    //todo:别人的写法　　比较高级　但是比较费脑　　

    // 定义：在以 root 为根的二叉树中寻找值为 val 的节点
    TreeNode find2(TreeNode root, int val) {
        // base case
        if (root == null) {
            return null;
        }
        // 看看 root.val 是不是要找的
        if (root.val == val) {
            return root;
        }
        // root 不是目标节点，那就去左子树找
        TreeNode left = find2(root.left, val);
        //todo:这俩个if  是为了 减少不必要的查询　
        if (left != null) {
            return left;
        }
        // 左子树找不着，那就去右子树找
        TreeNode right = find2(root.right, val);
        if (right != null) {
            return right;
        }
        // 实在找不到了
        return null;
    }


/**
    下面的代码实际运行的效率会低一些，原因也很简单，
    如果你能够在左子树找到目标节点，还有没有必要去右子树找了？没有必要。
    但这段代码还是会去右子树找一圈，所以效率相对差一些*/

    TreeNode find3(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        // 前序位置
        if (root.val == val) {
            return root;
        }
        // root 不是目标节点，去左右子树寻找
        TreeNode left = find3(root.left, val);
        TreeNode right = find3(root.right, val);
        // 看看哪边找到了
        return left != null ? left : right;
    }


/**
 这段代码相当于你先去左右子树找，然后才检查root，
    依然可以到达目的，但是效率会进一步下降。
    因为这种写法必然会遍历二叉树的每一个节点。*/

    TreeNode find4(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        // 先去左右子树寻找
        TreeNode left = find4(root.left, val);
        TreeNode right = find4(root.right, val);
        // 后序位置，看看 root 是不是目标节点
        if (root.val == val) {
            return root;
        }
        // root 不是目标节点，再去看看哪边的子树找到了
        return left != null ? left : right;
    }


//    现在不让你找值为val的节点，而是寻找值为val1或val2的节点
    TreeNode find5(TreeNode root, int val1,int val2) {
        // base case
        if (root == null) {
            return null;
        }
        // 看看 root.val 是不是要找的
        if (root.val == val1||root.val==val2) {
            return root;
        }
        // root 不是目标节点，那就去左子树找
        TreeNode left = find5(root.left, val1,val2);

        TreeNode right = find5(root.right, val1,val2);

        return left!=null?left:right;
    }


//寻找 二叉树中节点值为ｖａｌ１　与ｖａｌ２的最近公共节点
    TreeNode find6(TreeNode root, int val1,int val2) {
        // base case
        if (root == null) {
            return null;
        }
        //todo:前两个返回是方法自身的返回
        // 看看 root.val 是不是要找的
        if (root.val == val1||root.val==val2) {
            return root;
        }
        // root 不是目标节点，那就去左子树找
        TreeNode left = find6(root.left, val1,val2);
//        //todo:这俩个if  是为了 减少不必要的查询　
//        if (left != null) {
//            return left;
//        }
//        // 左子树找不着，那就去右子树找
        TreeNode right = find6(root.right, val1,val2);
//        if (right != null) {
//            return right;
//        }
//todo:这两个返回是ｒｏｏｔ的俩个子树递归完之后　　root自身函数调用的返回结果
        if (left!=null&&right!=null){
            return  root;
        }

        // 实在找不到了
        return left!=null?left:right;
    }


    TreeNode find7(TreeNode root, int val1,int val2) {
        if (root == null) {
            return null;
        }
        // 先去左右子树寻找
        TreeNode left = find7(root.left, val1,val2);
        TreeNode right = find7(root.right, val1,val2);

        // 后序位置，看看 root 是不是目标节点
        if (left!=null&&right!=null) {
            return root;
        }
        // root 不是目标节点，再去看看哪边的子树找到了
        return left != null ? left : right;
    }





    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);

        treeNode1.left=treeNode3;
        treeNode3.left=treeNode2;
        treeNode3.right=treeNode4;


        LookElement lookElement = new LookElement();

        TreeNode treeNode = lookElement.find(treeNode1, 2);
        if (treeNode!=null){
            System.out.println(treeNode.val);
        }
        else {
            System.out.println("二叉树中不含有此数值的节点");
        }


        TreeNode lookElement2 = lookElement.find6(treeNode1, 2,4);
        if (lookElement2!=null){
            System.out.println(lookElement2.val);
        }
        else {
            System.out.println("二叉树中不含有此数值的节点");
        }

    }

}
